package lcof2

import "math/rand"

// Solution https://leetcode.cn/problems/cuyjEf/
type Solution struct {
	presum []int
}

func Constructor(w []int) Solution {
	pre := make([]int, len(w)+1)
	for i, v := range w {
		pre[i+1] = pre[i] + v
	}
	return Solution{presum: pre}
}

func (t *Solution) PickIndex() int {
	seed := rand.Intn(t.presum[len(t.presum)-1]) + 1
	left, right := 0, len(t.presum)-1
	for mid := (left + right) / 2; left <= right; mid = (left + right) / 2 {
		if t.presum[mid] >= seed {
			right = mid - 1
		} else {
			left = mid + 1
		}
	}
	return left - 1
}
